package com.zp.self.module.level_4_算法练习.算法.二分查找;

/**
 * @author By ZengPeng
 */
public class 力扣_34_在排序数组中查找元素的第一个和最后一个位置 {
    //测试
    public static void main(String[] args) {
        int[] ints =null;

        ints= new 力扣_34_在排序数组中查找元素的第一个和最后一个位置().searchRange(new int[]{6,8,8,8,8,8,8}, 8);
        System.out.println(ints[0]+","+ints[1]);

        ints = new 力扣_34_在排序数组中查找元素的第一个和最后一个位置().searchRange(new int[]{5,7,7,8,8,10}, 6);
        System.out.println(ints[0]+","+ints[1]);

        ints = new 力扣_34_在排序数组中查找元素的第一个和最后一个位置().searchRange(new int[]{}, 0);
        System.out.println(ints[0]+","+ints[1]);
    }

    /**
    题目：给定一个按照升序排列的整数数组 nums，和一个目标值 target。
     找出给定目标值在数组中的开始位置和结束位置。
     如果数组中不存在目标值 target，返回 [-1, -1]。
     进阶：
     你可以设计并实现时间复杂度为 O(log n) 的算法解决此问题吗？

     示例 1：
     输入：nums = [5,7,7,8,8,10], target = 8
     输出：[3,4]

     示例 2：
     输入：nums = [5,7,7,8,8,10], target = 6
     输出：[-1,-1]

     示例 3：
     输入：nums = [], target = 0
     输出：[-1,-1]


    分析：【P 💗💖💘】
       1.使用二分法快速找到目标值
            a.如果没有,返回[-1,-1]
            b.如果有，再次使用二分法，向两边扩展
            -- 执行用时：0 ms, 在所有 Java 提交中击败了100.00%的用户
       2.分别找到第一个大于target,第一个小于target的下标，【找要插入的新位置即可】
            -- 执行用时：0 ms, 在所有 Java 提交中击败了100.00%的用户

    边界值 & 注意点：
       1.
     **/
    public int[] searchRange(int[] nums, int target) {
        //2.分别找到第一个大于target,第一个小于target的下标
        int left =0 ,right =nums.length-1,mid;
        while (left<=right){ //值在【left,right】中找:第一个小于target的数，找要插入的新位置即可
            mid = left+(right-left)/2;
            if(nums[mid]>=target)
                right=mid-1;
            else
                left=mid+1;
        }
        int newLeft=left;
        right =nums.length-1;
        while (newLeft<=right){ //值在【left,right】中找:第一个大于target的数,找要插入的新位置即可
            mid = newLeft+(right-newLeft)/2;
            if(nums[mid]<=target)
                newLeft=mid+1;
            else
                right=mid-1;
        }
        if(left>right)
            return new int[]{-1,-1};
        return  new int[]{left,right};
        // 1.使用二分法快速找到目标值 + 再次使用二分法，向两边扩展
       /* int left =0,right=nums.length-1;
        int x = -1;
        while (left<=right){
            int mid = left+(right-left)/2;
            if(nums[mid]>target){
                right = mid-1;
            }else if (nums[mid]<target){
                left = mid+1;
            }else {
                x= mid;break;
            }
        }
        if(x==-1) return new int[]{-1,-1};
        //向两边扩展
        left =0;right=x;
        while (left<=right){
            int mid = left+(right-left)/2;
            if(nums[mid]!=target)
                left = mid +1;
            else
                right=mid-1;
        }
        right=nums.length-1;
        while (x<=right){
            int mid = x+(right-x)/2;
            if(nums[mid]!=target)
                right = mid-1;
            else
                x = mid+1;
        }
        return new int[]{left,right};*/
    }
}
